package 链表题.判环算法;

import 链表题.ListNode;

/**
 * 龟兔赛跑算法
 */

public class Test1 {
    // 第一阶段: 判断是否有环
    /**
     * 如果换上存在环, 那么在环上一不同速度的两个指针必定会在某个时刻相遇
     */

    public static boolean hasCycle(ListNode head) {
        ListNode h = head;
        ListNode t = head;
        while(h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            if (t == h) {
                return true;
            }
        }
        return false;
    }

    // 第二阶段: 检查环入口节点
    public static ListNode detectCycle(ListNode head) {
        ListNode h = head;
        ListNode t = head;
        while(h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            if (t == h) {
                // 进入阶段二
                h = head;
                if (t == h) {
                    return head;
                }
                while (t != h) {
                    t= t.next;
                    h = h.next;
                }
                return h;
            }
        }
        return null;
    }


    public static void main(String[] args) {
        // 构造一个带环链表
        ListNode n12 = new ListNode(12, null);
        ListNode n11 = new ListNode(11, n12);
        ListNode n10 = new ListNode(10, n11);
        ListNode n9 = new ListNode(9, n10);
        ListNode n8 = new ListNode(8, n9);
        ListNode n7 = new ListNode(7, n8);
        ListNode n6 = new ListNode(6, n7);
        ListNode n5 = new ListNode(5, n6);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);
        n12.next = n7;
        System.out.println(hasCycle(n1));
        System.out.println(detectCycle(n1) == null ? null : detectCycle(n1).val);
    }
}
